class Solution {
 public:
  // double myPow(double x, int n) {  // 1.00000 -2147483648
  double myPow(double x, long n) {
    if (n == 0) return 1;
    if (n < 0) {
      x = 1 / x;
      n = -n;
    }
    if (x == 1) return 1;
    // return myPow(x,n-1)*x;  //输入为0.00001 2147483647时爆栈
    if ((n % 2) == 0) {
      // 分治思想：分
      double square = myPow(x, n / 2);
      // 分治思想：合，下面同理
      return square * square;
    } else {
      // 是奇数的时候
      double square = myPow(x, (n - 1) / 2);
      return square * square * x;
    }
  }
};
/*
作者：liweiwei1419
链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/di-gui-xie-fa-fen-zhi-si-xiang-yu-fei-di-gui-xie-f/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/